package com.peng.leetcode.tree;

/**
 * Flatten1
 *
 * 原地将二叉树展开为链表
 *
 * @author: lupeng6
 * @create: 2021/1/28 17:53
 */
public class Flatten1 {

    public static void main(String[] args) {
        TreeNode treeNode = TreeMain.array2tree(new Integer[]{1, 2, 5, 3, 4, null, 6});
        new Flatten1().flatten(treeNode);
        System.out.println(treeNode);
    }

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            TreeNode leftTreeRightmost = findLeftTreeRightmost(root.left);
            leftTreeRightmost.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        flatten(root.right);
    }

    /**
     * 查找左子树最右边的节点
     *
     * @author lupeng6
     * @date 2021/1/28 17:55
     */
    private TreeNode findLeftTreeRightmost(TreeNode node) {
        if (node.right == null) {
            return node;
        }
        return findLeftTreeRightmost(node.right);
    }
}
